package test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * @author Marioszk
 * 最长公共前缀
 * lettcode 14
 */
public class LongestCommonPrefix_最长公共前缀 {

    public static void main(String[] args) {
        String[] arr = new String[]{"cir", "car"};
        System.out.println(longestCommonPrefix2(arr));
    }

    public static String longestCommonPrefix(String[] strs) {
        StringBuilder sb = new StringBuilder();
        List<String> list = Arrays.stream(strs)
                .sorted(Comparator.comparingInt(s -> s.length()))
                .collect(Collectors.toList());
        int minLength = list.get(0).length();
        String firstStr = list.get(0);
        for (int i = 0; i < minLength; i++) {
            Set<Character> set = new HashSet<>();
            boolean common = true;
            for (int j = 0; j < list.size(); j++) {
                if (j == 0) {
                    set.add(list.get(j).charAt(i));
                } else if (set.add(list.get(j).charAt(i))) {
                    common = false;
                    break;
                }
            }
            if (common == true) {
                sb.append(firstStr.charAt(i));
            } else {
                break;
            }
        }
        return sb.toString();
    }

    public static String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    public static String longestCommonPrefix(String str1, String str2) {
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        return str1.substring(0, index);
    }
}
